﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace VRP_SM
{
    class Heuristics
    {
        public static CVRPSolution SavingsMethod(CVRPData vrpData)
        {
            List<Node> nodeList = vrpData.NodeList;
            double capacity = vrpData.Capacity;
            double? bestKnown = vrpData.BestKnownSolution;
            int n = vrpData.Dimension;

            // Initialize the routes, each customer node forms a route with the depot
            List<Path> routeList = new List<Path>();                                                // define a route list
            for (int i = 1; i < nodeList.Count; i++)                                                // for each customer node  
            {
                routeList.Add(new Path(new List<Node>() { nodeList[0], nodeList[i], nodeList[0] }));// create route list
            }

            // Initialize the savings list for each node pair (i,j)
            List<Savings> savingsList = new List<Savings>();                                        // define a saving list
            for (int i = 1; i < nodeList.Count - 1; i++)
            {
                for (int j = i + 1; j < nodeList.Count; j++)
                {
                    savingsList.Add(new Savings(i, j, nodeList[0], nodeList[i], nodeList[j]));      // create saving list
                }
            }

            // Sort the savings list in decreasing order
            var sortedSavingsList = from element in savingsList
                                    orderby element.S descending
                                    select element;

            // Combine routes
            Path r1 = null;                                                                         // route includes node i 
            Path r2 = null;                                                                         // route includes node j
            Node ndi = null;                                                                        // node list i
            Node ndj = null;                                                                        // node list j

            foreach (Savings sij in sortedSavingsList)
            {
                int i = sij.I;                                                                      // i of node pair (i,j) on saving list
                int j = sij.J;                                                                      // j of node pair (i,j) on saving list

                ndi = nodeList[i];
                ndj = nodeList[j];

                r1 = ndi.onPath;
                r2 = ndj.onPath;

                //check if node i and node j belong to different routes, and the load of two routes is less than the capacity
                if (r1 != r2 && (r1.Load + r2.Load) <= capacity)
                {
                    int index1 = r1.AllNodes.Count;                                                 // the count of all nodes on route1
                    int index2 = r2.AllNodes.Count;                                                 // the count of all nodes on route2

                    //check if node i is the first node of the path
                    if (ndi == r1.AllNodes[1])
                    {
                        //check if node j is the first node of the path
                        if (ndj == r2.AllNodes[1])
                        {
                            r1.AllNodes.RemoveAt(0);                                                // remove the node with index = 0 on route1
                            r1.AllNodes.Reverse();                                                  // reverse the order of the rest nodes on route1
                            r2.AllNodes.RemoveAt(0);                                                // remove the node with index = 0 on route2

                            routeList.Remove(r1);                                                   // remove route1 (arc (0,i))from route list
                            routeList.Remove(r2);                                                   // remove route2 (arc (j,0))from route list
                            routeList.Add(new Path(r1.AllNodes.Concat(r2.AllNodes).ToList()));      // add a new path (i,j)
                            continue;
                        }
                        //check if node j is the last node of the path
                        if (ndj == r2.AllNodes[index2 - 2])
                        {
                            r2.AllNodes.RemoveAt(index2 - 1);                                       // remove the node with index = index2-1 on route2
                            r1.AllNodes.RemoveAt(0);                                                // remove the node with index = 0 on route1

                            routeList.Remove(r1);                                                   // remove r1 (arc (0,i))from route list
                            routeList.Remove(r2);                                                   // remove r2 (arc (j,0))from route list
                            routeList.Add(new Path(r2.AllNodes.Concat(r1.AllNodes).ToList()));      // add a new path (j,i)
                            continue;
                        }
                    }
                    //check if node i is the last node of the path
                    if (ndi == r1.AllNodes[index1 - 2])
                    {
                        //check if node j is the first node of the path
                        if (ndj == r2.AllNodes[1])
                        {
                            r1.AllNodes.RemoveAt(index1 - 1);
                            r2.AllNodes.RemoveAt(0);

                            routeList.Remove(r1);
                            routeList.Remove(r2);
                            routeList.Add(new Path(r1.AllNodes.Concat(r2.AllNodes).ToList()));
                            continue;
                        }
                        //check if node j is the last node of the path
                        if (ndj == r2.AllNodes[index2 - 2])
                        {
                            r1.AllNodes.RemoveAt(index1 - 1);
                            r2.AllNodes.Reverse();
                            r2.AllNodes.RemoveAt(0);

                            routeList.Remove(r1);
                            routeList.Remove(r2);
                            routeList.Add(new Path(r1.AllNodes.Concat(r2.AllNodes).ToList()));
                        }
                    }
                }
            }

            double totalCost = 0;

            for (int i = 0; i < routeList.Count; i++)
                totalCost += routeList[i].Length;

            CVRPSolution solution = new CVRPSolution();
            solution.TotalCost = totalCost;
            solution.TourList = routeList;

            Console.WriteLine("Savings methods done.\nTotalcost : " + totalCost);
            return solution;
        }
    }
}
